package org.xqh.study.leetcode.algorithm;

import java.util.*;

/**
 * @ClassName FbnqTest
 * @Description 算法 测试代码
 * @Author xuqianghui
 * @Date 2021/1/4 10:07
 * @Version 1.0
 */
public class AlgorithmTest {

    public static void main11(String[] args) {
//        System.out.println(fib(0));
//        int[] nums = {1, 2, 3, 5, 12, 18, 21};
//        System.out.println(JSON.toJSONString(sumTest(nums, 15)));
//        int[] nums = new int[0];
//        System.out.println(nums.length);s
        // 68DE7A04D28ADE9D9D211414DAB699ED

        //EB244E90-E83D-450D-93CC-05C08B18C610  68DE7A04D28ADE9D9D211414DAB699ED
//        ListNode l1 = new ListNode(3, new ListNode(5));
//        ListNode l2 = new ListNode(2);
//        ListNode ret = addTwoNumbers(l1, l2);
//        System.out.println("....");
    }

    /**
     * https://leetcode-cn.com/problems/fibonacci-number/
     * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。
     * 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     */
    public static int fib(int n) {
        int[] arr = new int[n + 1];
        arr[0] = 0;
        if (n == 0) {
            return 0;
        }
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    /**
     * https://leetcode-cn.com/problems/two-sum/
     * 数组 中 两数之和 = target
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] sumTest(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    /**
     * https://leetcode-cn.com/problems/two-sum/
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode();
        recursionPutNode(l1, l2, ret, false);
        return ret;
    }

    public static void recursionPutNode(ListNode l1, ListNode l2, ListNode ret, boolean plus) {
        if (l1 == null && l2 == null && !plus) {
            return;
        }
        int a = null != l1 ? l1.val : 0;
        int b = null != l2 ? l2.val : 0;
        int c = a + b + (plus ? 1 : 0);
        ListNode l1n = null != l1 ? l1.next : null;
        ListNode l2n = null != l2 ? l2.next : null;
        if (c >= 10) {
            ret.val = c - 10;
            ret.next = new ListNode();
            recursionPutNode(l1n, l2n, ret.next, true);
        } else {
            ret.val = c;
            if (null != l1n || null != l2n) {
                ret.next = new ListNode();
                recursionPutNode(l1n, l2n, ret.next, false);
            }
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 搜索二维矩阵
     * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean searchMatrix11(int[][] matrix, int target) {
        boolean result = false;
        a:
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            b:
            for (int j = 0; j < row.length; j++) {
                if (row[j] == target) {
                    result = true;
                    break a;
                }

                if (row[j] > target) {
                    break b;
                }
            }
        }
        return result;
    }

    public static void main333(String[] args) {
//        int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        int[][] matrix = {{-1, 3}};
        System.out.println(searchMatrix2(matrix, -1));
        ;
    }

    /**
     * 二分法查找
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean searchMatrix2(int[][] matrix, int target) {
        boolean result = false;
        a:
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            int left = 0, right = row.length - 1;
            while (left != right) {
                int mid = left + (right - left + 1) / 2;
                if (row[mid] > target) {
                    right = (mid - 1) < left ? left : (mid - 1);
                } else if (row[mid] == target) {
                    result = true;
                    break a;
                } else {
                    left = (mid + 1) > right ? right : (mid + 1);
                }
            }
            if (row[left] == target) {
                result = true;
                break a;
            }
        }
        return result;
    }


    private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].length - 1 : matrix.length - 1;

        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            if (vertical) { // searching a column
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else { // searching a row
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean searchMatrix33(int[][] matrix, int target) {
        // an empty matrix obviously does not contain `target`
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        // iterate over matrix diagonals
        int shorterDim = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < shorterDim; i++) {
            boolean verticalFound = binarySearch(matrix, target, i, true);
            boolean horizontalFound = binarySearch(matrix, target, i, false);
            if (verticalFound || horizontalFound) {
                return true;
            }
        }

        return false;
    }


    /**
     * 最优解  选取 左下角坐标
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int col = 0;
        int row = matrix.length - 1;
        while (col < matrix[0].length && row >= 0) {
            if (matrix[row][col] > target) {
                row--;
            } else if (matrix[row][col] < target) {
                col++;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 数组合并
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge11(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        System.arraycopy(nums2, 0, nums1, m, n);
        for (int i = m; i < m + n; i++) {
            int tmp = nums1[i];
            for (int j = i - 1; j >= 0; j--) {
                if (nums1[j] > tmp) {
                    int cur = nums1[j];
                    nums1[j] = tmp;
                    nums1[j + 1] = cur;
                } else {
                    break;
                }
            }
        }
    }

    public static void main123(String[] args) {
        int[] nums1 = {4, 5, 6, 0, 0, 0};
        int[] nums2 = {1, 2, 3};
        merge(nums1, 3, nums2, 3);
    }

    /**
     * 新建临时 数组
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge22(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        int[] tmp = new int[m + n];
        int n1 = 0, n2 = 0;
        for (int i = 0; i < tmp.length; i++) {
            int val1 = (n1 == m) ? Integer.MAX_VALUE : nums1[n1];
            int val2 = (n2 == n) ? Integer.MAX_VALUE : nums2[n2];
            if (val1 < val2) {
                tmp[i] = nums1[n1];
                n1++;
            } else {
                tmp[i] = nums2[n2];
                n2++;
            }
        }
        System.arraycopy(tmp, 0, nums1, 0, m + n);
    }

    /**
     * 不使用临时 数组
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        int n1 = m - 1, n2 = n - 1;
        for (int i = m + n - 1; i >= 0; i--) {
            int val1 = (n1 < 0) ? Integer.MIN_VALUE : nums1[n1];
            int val2 = (n2 < 0) ? Integer.MIN_VALUE : nums2[n2];
            if (val1 > val2) {
                nums1[i] = val1;
                n1--;
            } else {
                nums1[i] = val2;
                n2--;
            }
        }
    }

    /**
     * https://leetcode-cn.com/problems/super-egg-drop/
     * 鸡蛋掉落 确定 F ( 0<=F<= N超过这个楼层 鸡蛋会碎)
     *
     * @param K 鸡蛋个数
     * @param N 楼层
     * @return
     */
    public static int superEggDrop(int K, int N) {
        int left = 0, right = N - 1;
        int count = 0;
        while (right > left) {
            int mid = left + (right - left + 1) / 2;
            right = mid - 1;
            count++;
        }
        return count;//TODO
    }

    public static void main(String[] args) {
        System.out.println(eggDrop(3, 104));
    }
    /**
     * 鸡蛋掉落问题
     *
     * @param K K个鸡蛋
     * @param N N层楼
     *          状态转义方程 (K个鸡蛋, N层楼, 从X层开始扔)
     *          kp(K, X) = max(kp(K - 1, X - 1), kp(K, N - X))
     *          如果 有 0 到 N 种扔法,  取 其中的最小值 就是结果 F (最小移动次数)
     * @return
     */
    public static int eggDrop(int K, int N) {
        int[][] egg = new int[K+1][N+1];
        //如果 是 1个鸡蛋, 对应N层楼, 最大移动次数 为 N ,  只能从第一层开始扔 才能确定F
        for(int i = 1; i <= K; i ++){
            for(int j = 1; j <= N; j ++){
                if(i == 1){
                    egg[i][j] = j;
                }else {
                    egg[i][j] = -1;
                }
            }
        }

        int res = dp2(K, N, egg);
        //打印 结构 是否正确
        return res;
    }


    public static int dp2(int K, int N, int[][] egg){
        if(N == 0){
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for(int i = 1; i <= N; i ++){
            int subRes = dpEggDrop(K, i, N, egg);
            res = Math.min(res, subRes);
        }
        egg[K][N] = res;
        return res;
    }

    public static int dpEggDrop(int K, int X, int N, int[][] egg){
        //鸡蛋碎
        int breakRet = dp2(K - 1, X - 1, egg);
        //鸡蛋不碎
        int nonBreakRet = dp2(K, N - X, egg);

        int result =  Math.max(breakRet, nonBreakRet) + 1;
        return result;
    }

    static  Map<Integer, Integer> retMap = new HashMap<>();
    public static int dp(int K, int N){
        //因为 1 <= K <= 100
        Integer key = N * 100 + K;
        if(retMap.containsKey(key)){
            return retMap.get(key);
        }

        if(K == 1){
            return N;
        }

        if(N == 0){
            return 0;
        }

        int left = 1, right = N;
        while (left + 1 < right){
            int mid = (left + right)/2;
            int t1 = dp(K - 1, mid - 1);
            int t2 = dp(K, N - mid);
            if(t1 < t2){
                left = mid;
            }else if(t1 > t2){
                right = mid;
            }else{
                left = right = mid;
            }
        }
        int result = 1 + Math.min(Math.max(dp(K - 1, left - 1), dp(K, N - left)), Math.max(dp(K - 1, right - 1), dp(K, N - right)));
        retMap.put(key, result);
        return result;
    }

    public static void main22(String[] args) {
//        System.out.println(dp(2, 3));

        int[] arr = {3, 2, 4, 2, 1};
        System.out.println(findDuplicate(arr));
    }

    /**
     * 找出 重复的数字
     * https://leetcode-cn.com/problems/find-the-duplicate-number/
     * @param nums
     * @return
     */
    public static int findDuplicate(int[] nums) {
        for(int i = 0; i < nums.length; i ++){
            while (nums[i] != i + 1){
                int tmp = nums[nums[i] - 1];//对应 坐标的值
                if(nums[nums[i] - 1] == nums[i]){
                    return nums[i];
                }
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
            }
        }
//        int[] freq = new int[nums.length];
//        for(int i = 0; i < nums.length; i++){
//            if(freq[nums[i]] > 0){
//                return nums[i];
//            }
//            freq[nums[i]]++;
//        }
        return -1;
    }

    /**
     * https://leetcode-cn.com/problems/sliding-puzzle/
     * 滑动谜题
     * @param board
     * @return
     */
    public int slidingPuzzle(int[][] board) {
        int R = board.length, C = board[0].length;
        int sr = 0, sc = 0;
        search:
        for (sr = 0; sr < R; sr++)
            for (sc = 0; sc < C; sc++)
                if (board[sr][sc] == 0)
                    break search;

        int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Queue<Node> queue = new ArrayDeque();
        Node start = new Node(board, sr, sc, 0);
        queue.add(start);

        Set<String> seen = new HashSet();
        seen.add(start.boardstring);

        String target = Arrays.deepToString(new int[][]{{1,2,3}, {4,5,0}});

        while (!queue.isEmpty()) {
            Node node = queue.remove();
            if (node.boardstring.equals(target))
                return node.depth;

            for (int[] di: directions) {
                int nei_r = di[0] + node.zero_r;
                int nei_c = di[1] + node.zero_c;

                if ((Math.abs(nei_r - node.zero_r) + Math.abs(nei_c - node.zero_c) != 1) ||
                        nei_r < 0 || nei_r >= R || nei_c < 0 || nei_c >= C)
                    continue;

                int[][] newboard = new int[R][C];
                int t = 0;
                for (int[] row: node.board)
                    newboard[t++] = row.clone();
                newboard[node.zero_r][node.zero_c] = newboard[nei_r][nei_c];
                newboard[nei_r][nei_c] = 0;

                Node nei = new Node(newboard, nei_r, nei_c, node.depth+1);
                if (seen.contains(nei.boardstring))
                    continue;
                queue.add(nei);
                seen.add(nei.boardstring);
            }
        }

        return -1;
    }

    public static class Node {
        int[][] board;
        String boardstring;
        int zero_r;
        int zero_c;
        int depth;
        Node(int[][] B, int r, int c, int d) {
            board = B;
            boardstring = Arrays.deepToString(board);
            zero_r = r;
            zero_c = c;
            depth = d;
        }
    }
}
